package leetcode;

/**
 * @Classname CanCompleteCircuit_0134
 * @Author happytaohaha
 * @Date 2020/3/24
 * @Description 134. 加油站
 */
public class CanCompleteCircuit_0134 {

    /**
     * O(N^2)
     * @param gas
     * @param cost
     * @return
     */
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = gas[i] - cost[i];
        }

        for (int i = 0; i < len; i++) {

            if (res[i] >= 0) {
                int sum = 0;
                int k = i;
                for (int j = 0; j < len; j++) {
                    sum +=res[k];
                    if(sum < 0){
                        break;
                    }else{
                        k++;
                        k = k % len;
                    }
                }
                if(sum >=0){
                    return i;
                }
            }
        }
        return -1;
    }


    /**
     * 其实i从第一个走碰见小于0 的都是非法解答，然后重新从 i+1 开始走，curr_tank=0 重置
     * @param gas
     * @param cost
     * @return
     */
        public int canCompleteCircuit2(int[] gas, int[] cost) {
            int n = gas.length;

            int total_tank = 0;
            int curr_tank = 0;
            int starting_station = 0;
            for (int i = 0; i < n; ++i) {
                total_tank += gas[i] - cost[i];
                curr_tank += gas[i] - cost[i];
                // If one couldn't get here,
                if (curr_tank < 0) {
                    // Pick up the next station as the starting one.
                    starting_station = i + 1;
                    // Start with an empty tank.
                    curr_tank = 0;
                }
            }
            return total_tank >= 0 ? starting_station : -1;
        }


    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{2},new int[]{2}));
    }



}
